# 组合：https://leetcode-cn.com/problems/combinations/

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        rst = []
        nums = [i for i in range(1, n + 1)]
        used = [False] * n
        def cmb(arr):
            if len(arr) == k:
                rst.append(arr[:])
                return 
            
            for i in range(len(nums)):
                # 1. 去掉重复使用元素： 下面的 判断，包含了这一条件可以去掉
                if used[i] == True:
                    continue
                # 2. 保证，使用的元素在当前元素后面，避免[1, 3][3, 1]的情况出现
                if arr and nums[i] <= arr[-1]:
                    continue
                arr.append(nums[i])
                used[i] = True
                cmb(arr)
                used[i] = False
                arr.pop()
        
        cmb([])
        return rst